//题目:
// 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
// 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
// 同一个单元格内的字母不允许被重复使用。
#include<iostream>
#include<vector>
#include<set>

using namespace std;
//代码:
class Solution 
{
    string str;
    int arr_x[4]={-1,1,0,0},arr_y[4]={0,0,-1,1};//方向矢量
    bool flag[6][6]={false};//标记board中的某个位置上的元素是否被使用过
public:
    bool dfs(vector<vector<char>>& board,int row,int col,int pos)
    {
        if(pos>=str.size())return true;

        //从board的(row,col)点处,判断相邻位置(上、下、左、右)是否存在str[pos]
        for(int i=0;i<4;i++)
        {
            int x=row+arr_x[i],y=col+arr_y[i];
            if(x>=0 && x<board.size() && y>=0 && y<board[0].size() && flag[x][y]==false && board[x][y]==str[pos])
            {
                //标记这个位置
                flag[x][y]=true;
                if(dfs(board,x,y,pos+1)==true)return true;;//寻找下一个字母
                //回溯
                flag[x][y]=false;
            }
        }
        //如果相邻找不着str[pso]，则失败
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) 
    {
        str=word;
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[i].size();j++)
            {
                if(board[i][j]==str[0])
                {
                    flag[i][j]=true;
                    if(dfs(board,i,j,1)==true)return true;
                    flag[i][j]=false;//回溯
                }
            }
        }
        return false;
    }
};